import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 03010570
 * @date 2020/07/07
 * describe:    LeetCode:112、 路径之和  https://leetcode-cn.com/problems/path-sum/
 */
public class LeetCode_112 {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(5);
        TreeNode nodeLeft1 = new TreeNode(4);
        TreeNode noderight = new TreeNode(8);
        noderight.left = new TreeNode(13);
        TreeNode noderight2 = new TreeNode(4);
        noderight2.right = new TreeNode(1);
        TreeNode nodeLeft2 = new TreeNode(11);
        nodeLeft2.left = new TreeNode(7);
        nodeLeft2.right = new TreeNode(3);
        nodeLeft1.left = nodeLeft2;
        noderight.right = noderight2;
        treeNode.left = nodeLeft1;
        treeNode.right = noderight;
        LeetCode_112 code112 = new LeetCode_112();
        System.out.println(code112.hasPathSum3(treeNode, 22));
    }

    public boolean hasPathSum3(TreeNode root, int sum) {
        return dfs(root,sum,0);
    }

    private boolean dfs(TreeNode root, int sum, int i) {
        if(root == null){
            return false;
        }
        i +=root.val;
        if(root.left == null && root.right == null){
            return sum == i;
        }
        return dfs(root.left,sum,i)|| dfs(root.right ,sum,i);
    }


    /**
         * BFS ： 迭代
         *  时间复杂度 ：O(N)
         *  空间复杂度 ：O(N) ，两个队列的开销
         * @param root
         * @param sum
         * @return
         */
    public boolean hasPathSum2(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        Queue<TreeNode> queueNode = new LinkedList<>();
        Queue<Integer> queueVal = new LinkedList<>();
        queueNode.offer(root);
        queueVal.offer(root.val);
        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            Integer val = queueVal.poll();
            // 叶子结点
            if (node.left == null && node.right == null) {
                if (sum == val) {
                    return true;
                }
                continue;
            }
            // 左子树添加至 队列
            if (node.left != null) {
                queueNode.offer(node.left);
                queueVal.offer(val + node.left.val);
            }
            // 右子树添加至 队列
            if (node.right != null) {
                queueNode.offer(node.right);
                queueVal.offer(val + node.right.val);
            }
        }
        return false;


    }

    /**
     * DFS 一层层地轨道 叶子结点进行判断
     * 时间复杂度：O(N)  遍历树的节点一遍
     * 空间复杂度：O(H)  H为树的高度，最坏的情况，树呈链状，空间复杂度 O(N)
     *
     * @param root
     * @param sum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return sum == root.val;
        }
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
    }


}
